package DP.子序列;


import java.util.HashMap;
import java.util.Map;

/*
    注意：删最少次数 不等于 删的char和最小 !

    双板子解本题不出错：
    1
        L+ci板子
    2
        终点 *
        单cur *
        迭代
        起点
 */
public class 最少删几次改成删的char和最小_583进阶版_712 {

    char[] s1,s2; int n1,n2;
    public int minimumDeleteSum(String w1, String w2) {
        s1=w1.toCharArray();s2=w2.toCharArray();n1=w1.length();n2=w2.length(); int i=n1-1,j=n2-1;
        return back(i, j);
    }
    private int back(int i, int j) {
        //看草图终点是-1
        if(i<0){
            int sum=0;
            for (int k = 0; k <= j; k++) {
                sum+=s2[k];
            }
            return sum;
        }
        if(j<0){
            int sum=0;
            for (int k = 0; k <= i; k++) {
                sum+=s1[k];
            }
            return sum;
        }
        //相同不删跳过
        if(s1[i]==s2[j]){
            return back(i-1,j-1);
        }
        //L+ci板子:要+1本身删的次数
        int a = back(i,j-1) + s2[j];
        int b = back(i-1,j) + s1[i];
        return Math.min(a,b);
    }
}
